#include<iostream>
#include<queue>
#include<vector>
#include<set>
using namespace std;

class MKAverage {
private: 
    long long mk_sum;
    int m, k;
    multiset<int> mk_min, mk_middle, mk_max;
    queue<int> q;
public:
    MKAverage(int m, int k) : mk_sum(0), m(m), k(k) {}
    
    void addElement(int num) {
        if (q.size() < m - 1) {
            mk_middle.insert(num);
            mk_sum += num;
        } else if (q.size() == m - 1) {
            mk_middle.insert(num);
            mk_sum += num;
            for (int i = 0; i < k; i++) {
                mk_min.insert(*mk_middle.begin());
                mk_sum -= *mk_middle.begin();
                mk_middle.erase(mk_middle.begin());
                mk_max.insert(*(mk_middle.rbegin()));
                mk_sum -= *mk_middle.rbegin();
                mk_middle.erase(prev(mk_middle.end()));
            }
        } else {
            if (num < *mk_min.rbegin()) {
                mk_sum += *mk_min.rbegin();
                mk_middle.insert(*mk_min.rbegin());
                mk_min.erase(prev(mk_min.end()));
                mk_min.insert(num);
            } else if (num > *mk_max.begin()) {
                mk_sum += *mk_max.begin();
                mk_middle.insert(*mk_max.begin());
                mk_max.erase(mk_max.begin());
                mk_max.insert(num);
            } else {
                mk_middle.insert(num);
                mk_sum += num;
            }
            if (mk_min.count(q.front())) {
                mk_min.erase(mk_min.find(q.front()));
                mk_min.insert(*mk_middle.begin());
                mk_sum -= *mk_middle.begin();
                mk_middle.erase(mk_middle.begin());
            } else if (mk_max.count(q.front())) {
                mk_max.erase(mk_max.find(q.front()));
                mk_max.insert(*mk_middle.rbegin());
                mk_sum -= *mk_middle.rbegin();
                mk_middle.erase(prev(mk_middle.end()));
            } else {
                mk_sum -= q.front();
                mk_middle.erase(q.front());
            }
            q.pop();
        }
        q.push(num);
    }
    
    int calculateMKAverage() {
        if (q.size() < m) {
            return -1;
        } else {
            return mk_sum / (m - 2 * k);
        }
    }
};

/**
 * Your MKAverage object will be instantiated and called as such:
 * MKAverage* obj = new MKAverage(m, k);
 * obj->addElement(num);
 * int param_2 = obj->calculateMKAverage();
 */

int main() {
    return 0;
}

/**
 * 2023.1.18
 * 三个有序队列
 * multiset的使用
*/